/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
// backtracking(i)表示选取包括i后的值，花费时间较多剪枝
// 剪枝1：对candidates排序，如果同一层找到答案，那么由于之后的数更大不可能是答案，直接break
var combinationSum = function(candidates, target) {
    const ans = []
    let path = [], len = candidates.length
    candidates.sort((a, b) => a - b)
    const backtracking = (i, target) => {
        if (target < 0) return
        if (target == 0) {
            ans.push(JSON.parse(JSON.stringify(path)))
            return true
        }
        for (let j = i; j < len; j++) {
            path.push(candidates[j])
            let found = backtracking(j, target - candidates[j])
            path.pop()
            if(found) break
        }
    }
    backtracking(0, target)
    return ans
 };
 // 剪枝2：不用对candidates排序，直接在处理过程中找到第一个成立的值，如果同层的大于当前那么直接跳过，复杂度还是高
 var combinationSum1 = function(candidates, target) {
    const ans = []
    let path = [], len = candidates.length
    const backtracking = (i, target) => {
        if (target < 0) return
        if (target == 0) {
            ans.push(JSON.parse(JSON.stringify(path)))
        }
        let val
        for (let j = i; j < len; j++) {
            path.push(candidates[j])
            let found = backtracking(j, target - candidates[j])
            path.pop()
            if(found) {
                val = candidates[j]
                if(candidates[j] > val) continue
            }
        }
    }
    backtracking(0, target)
    return ans
 };
 console.log(combinationSum([2], 1));